"""
使用分治的方法解决问题23。

在之前的算法中，如果数组的大小恰好是两个时，就回到了我们熟悉的领域。
从2个到扩展到多个时，都可以考虑通过分治算法解决，尽管不一定是最优解。

"""
from typing import List, Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:

    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        def merge_double(node1:Optional[ListNode],node2:Optional[ListNode])->Optional[ListNode]:
            if not node1:
                return node2
            if not node2:
                return node1
            rp=ListNode()
            temp=rp
            while node1 and node2:
                if node1.val<=node2.val:
                    temp.next = node1
                    node1=node1.next
                else:
                    temp.next=node2
                    node2=node2.next
                temp=temp.next
            if node1:
                temp.next=node1
            if node2:
                temp.next=node2
            return rp.next
        
        def merge_arr(lis:List[Optional[ListNode]])->Optional[ListNode]:
            if len(lis)==0:
                return None
            if len(lis)==1:
                return lis[0]
            mid=len(lis)//2
            left_node=merge_arr(lis[0:mid])
            right_node=merge_arr(lis[mid:len(lis)])
            return merge_double(left_node, right_node)

        return merge_arr(lists)

if __name__=='__main__':
    node1=ListNode(1,ListNode(4,ListNode(5)))
    node2=ListNode(1,ListNode(3,ListNode(4)))
    node3=ListNode(2,ListNode(6))
    lists=[None]

    s=Solution()
    res=s.mergeKLists(lists)
    lis=[]
    while res is not None:
        lis.append(res.val)
        res=res.next

    print(f'list:{lis}')

    pass